/**
 * https://leetcode-cn.com/problems/rotate-list/
 * 给你一个链表的头节点 head ，旋转链表，将链表每个节点向右移动 k 个位置。
 * 旋转链表
 * @param head 
 * @param k 
 */
 const rotateRight = (head: ListNode | null, k: number): ListNode | null => {
    // 边界判断
    if (head === null || head.next === null) return head

    // 找尾节点
    let cur = head,
        count = 0;

    // 找到尾节点
    while (cur.next !== null) {
        cur = cur.next;
        count++
    }

    // 要往前走的数字
    let add = count - k % count

    // 如果旋转完成后和n相等, 直接返回head
    if (add === count) return head;

    // 构造循环链表
    cur.next = head;

    while (add--) {
        // 往前轴
        cur = cur.next!;
    }

    // 最后cur.next就是要找的结果, 并且要将head.next断开
    const ans = cur.next;

    // 断开循环
    cur.next = null

    return ans
    
};


const rotateRight2 = (head: ListNode | null, k: number): ListNode | null => {
    // 边界判断
    if (head === null || head.next === null) return head

    // 存储节点的额
    const arr: ListNode[] = []

    let h: ListNode | null = head;
    while (h !== null) {
        // 存放到arr中
        arr.push(h)
        h = h.next;
    }

    let i = arr.length - 1;

    const dummyHead = new ListNode(0)
    dummyHead.next = head;

    while(k !== 0) {
        const last = arr[i].next!

        // 修改指向
        dummyHead.next = last
        last.next = dummyHead.next

        // 清除尾部元素
        arr[i].next = null

        i--;
        // 如果i小于0了, 让其恢复为最后的位置
        if (i < 0) i = arr.length - 1 
        k--
    }

    return dummyHead.next;
};